package com.yin.algorithms;

import com.yin.Sort;
import com.yin.Util;

public class QuickSort implements Sort {

    /*
    *
    *   low, high, pivot都只讨论数组的下标，并不代表在数组中的第几个元素
    * */

    @Override
    public void sort(int[] arr) {

        //low -> 需要找的比pivot大的数的下标
        //high -> 需要找的比pivot小的数的下标
        quickSort(arr, 0, arr.length - 1);
    }

    //划分函数
    private int partition(int[] arr, int low, int high) {

        //需要找的比pivot大的数的下标
        int i = low;

        //需要找的比pivot小的数的下标，因为arr[high]在分区后会被安放到正确位置所以忽略，从arr[high - 1]开始找
        int j = high - 1;

        //枢纽元素
        int pivot = arr[high];

        //当i和j不相遇时在循环中进行检索
        //下面两条while语句的(i < j)条件保证不会出现i和j相邻然后i++,j--同时进行，所以i和j一定会相遇
        while(i != j) {

            //i一直往右挪，直到遇到一个比pivot大的元素停止，此时i为这个数在原数组对应的下标
            //如果arr[i]比pivot小或等于pivot则继续往后寻找
            while(i < j && arr[i] <= pivot) i++;

            //j一直往左挪，直到遇到一个比pivot小的元素停止，此时j为这个数在原数组的下标
            //如果arr[j]比pivot大或等于pivot则继续往前寻找
            while(i < j && arr[j] >= pivot) j--;

        }

        //当i和j都停下，交换两个数的位置
        Util.swap(arr, i, j);

        //把枢纽元素放到正确位置
        //此时i = j，所以枢纽和i或j互换位置都是一样的
        Util.swap(arr, i, high);

        //本来是枢纽元素的位置应该是high，但上面要把枢纽元素放到正确位置(i/j)上，所以正确枢纽元素的值的下标应为交换后的(i/j)而非high
        //此时i == j，所以返回i和j都是一样的
        return i;
    }

    private void quickSort(int[] arr, int low, int high) {

        if(low >= high) return;

        //每次递归都会找出来一个正确元素, mid为它在原数组的下标
        //以此为界继续对此元素为中心的左右两个数组进行划分
        int mid = partition(arr, low, high);

        //对左半区继续划分
        quickSort(arr, low , mid - 1);

        //对右半区继续进行划分
        quickSort(arr, mid + 1, high);
    }
}
